package com.yuufa.test.matrix;

import com.yuufa.util.Tool;

public class Knapsack {

    public static void main(String[] args) {

        int knap = 8;
        Fruit[] s = { new Fruit(0, "李子", 4, 4500), new Fruit(1, "蘋果", 5, 5700), new Fruit(2, "橘子", 2, 2250),
                      new Fruit(3, "草莓", 1, 1100), new Fruit(4, "甜瓜", 6, 6700)};
        int n = s.length;
        int[] value = new int[knap + 1];
        Fruit[] result = new Fruit[knap + 1];

        // initial value[]
        for (int i = 0; i <= knap; i++) {
            value[i] = 0;
        }

        for (int i = 0; i < n; i++) {
            Fruit fruit = s[i];

            int weight = fruit.getWeight();
            int price = fruit.getPrice();
            
            for (int j = weight; j <= knap; j++) {
                if(value[j] < (price + value[j-weight])) {
                    value[j] = price + value[j-weight];
                    result[j] = fruit;
                }
            }
        }
        
        Tool.print(value, knap, knap);
        
        print(result, knap);
    }
    
    public static void print(Fruit[] f, int knap) {
        
        while(knap != 0) {
            Fruit fruit = f[knap];
            knap = knap - fruit.getWeight();
            
            System.out.printf("%4s", fruit.getName());
        }
    }
}

class Fruit {
    private Integer index;
    private String name;
    private Integer weight;
    private Integer price;

    public Fruit(Integer index, String name, Integer weight, Integer price) {
        this.index = index;
        this.name = name;
        this.weight = weight;
        this.price = price;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getWeight() {
        return weight;
    }

    public void setWeight(Integer weight) {
        this.weight = weight;
    }

    public Integer getPrice() {
        return price;
    }

    public void setPrice(Integer price) {
        this.price = price;
    }

    public Integer getIndex() {
        return index;
    }

    public void setIndex(Integer index) {
        this.index = index;
    }

}